//
// Created by madison on 2022/6/16.
// https://leetcode.cn/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/
//
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


class Solution {
public:
    vector<int> intersect(vector<int> &num1, vector<int> &num2) {
        if (num1.size() > num2.size()) {
            return intersect(num2, num1);
        }
        unordered_map<int, int> m;
        for (int num: num1) {
            ++m[num];
        }
        vector<int> intersection;
        for (int num: num2) {
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }

    vector<int> intersect1(vector<int> &nums1, vector<int> &nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        vector<int> intersection;
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            if (nums1[index1] < nums2[index2]) {
                index1++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                intersection.push_back(nums1[index1]);
                index1++;
                index2++;
            }
        }
        return intersection;
    }
};

void MyPrint(int val) {
    printf("%d ", val);
}

int main() {
    Solution solution;
    vector<int> v1 = {4, 9, 5};
    vector<int> v2 = {9, 4, 9, 8, 4};
    vector<int> v3 = solution.intersect1(v1, v2);
    for_each(v3.begin(), v3.end(), MyPrint);
}

